package com.datastructure2.stackandqueue;



import java.util.*;
import java.util.jar.Manifest;

/**
 * @author: 临晖
 * @date: 2023/12/22
 * @description:
 */
public class Solution {
    public boolean isValid(String s) {
        HashMap<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');

        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (stack.empty() && (ch == ')' || ch == '}' || ch == ']')) {
                return false;
            }

            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(map.get(ch));
            } else {
                Character pop = stack.pop();
                if (pop != ch) {
                    return false;
                }
            }
        }

        return stack.empty();
    }


    /**
     * 1047. 删除字符串中的所有相邻重复项
     * 提示
     * 简单
     * 598
     * 相关企业
     * 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
     * 在 S 上反复执行重复项删除操作，直到无法继续删除。
     * 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
     *
     * @param s
     * @return
     */
    public String removeDuplicates(String s) {
        //Stack<Character> stack = new Stack<>();
        //for (int i = 0; i <s.length(); i++) {
        //    char ch = s.charAt(i);
        //    if (!stack.empty()) {
        //        Character peek = stack.peek();
        //
        //        if (peek == ch) {
        //            stack.pop();
        //        } else {
        //            stack.push(ch);
        //        }
        //    } else {
        //        stack.push(ch);
        //    }
        //}
        //
        //s = "";
        //while (!stack.isEmpty()) {
        //    s += stack.pop();
        //}
        //
        //StringBuilder b = new StringBuilder(s);
        //return b.reverse().toString();

        char[] chars = s.toCharArray();

        int slow = -1;
        for (int i = 0; i < chars.length; i++) {
            if (slow == -1 || chars[slow] != chars[i]) {
                chars[++slow] = chars[i];
            } else {
                slow--;
            }
        }

        return new String(Arrays.copyOf(chars, slow + 1));
    }


    /**
     * 150. 逆波兰表达式求值
     * 中等
     * 846
     * 相关企业
     * 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
     * <p>
     * 请你计算该表达式。返回一个表示表达式值的整数。
     * <p>
     * 注意：
     * <p>
     * 有效的算符为 '+'、'-'、'*' 和 '/' 。
     * 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
     * 两个整数之间的除法总是 向零截断 。
     * 表达式中不含除零运算。
     * 输入是一个根据逆波兰表示法表示的算术表达式。
     * 答案及所有中间计算结果可以用 32 位 整数表示。
     *
     * @param tokens
     * @return
     */
    public int evalRPN(String[] tokens) {
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String str = tokens[i];
            if ("*".equals(str) || "-".equals(str) || "+".equals(str) || "/".equals(str)) {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                str = getRes(num2, num1, str);
            }

            stack.push(str);
        }

        return Integer.parseInt(stack.peek());
    }

    public String getRes(int num1, int num2, String ch) {
        int res = 0;
        switch (ch) {
            case "+":
                res = num1 + num2;
                break;
            case "-":
                res = num1 - num2;
                break;
            case "*":
                res = num1 * num2;
                break;
            case "/":
                res = num1 / num2;
                break;
        }
        return res + "";
    }


    /**
     *
     * 239. 滑动窗口最大值
     * 提示
     * 困难
     * 2.6K
     * 相关企业
     * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
     * 返回 滑动窗口中的最大值 。
     *
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        //思路一，超时
        //Stack<Integer> stack = new Stack<>();
        //int[] newNums = new int[nums.length - k + 1];
        //int count = 0;
        //int skip = -1;
        //for (int i = 0; i < nums.length; i++) {
        //    skip++;
        //    if (skip != k) {
        //        if (stack.empty()) {
        //            stack.push(nums[i]);
        //        } else {
        //            int num = stack.pop();
        //            int max = num > nums[i] ? num : nums[i];
        //            stack.push(max);
        //        }
        //    } else {
        //        newNums[count++] = stack.pop();
        //        i -= k;
        //        skip = -1;
        //    }
        //}
        //newNums[count] = stack.pop();
        //return newNums;


        //思路二
        MyQue que = new MyQue();
        int[] res = new int[nums.length - k + 1];
        int count = 0;

        //先装入前k个数字，这里要遵循：大于等于的，弹出上一个，小于的入队列
        for (int i = 0; i < k; i++) {
            que.push(nums[i]);
        }

        //找到第一个最大值
        int max = que.font();
        res[count++] = max;
        for (int i = k; i < nums.length; i++) {
            //添加
            que.push(nums[i]);
            //删除
            que.del(nums[i - k]);
            //取最大值
            res[count++] = que.font();
        }


        return res;
    }


    /**
     *
     * 347. 前 K 个高频元素
     * 中等
     * 1.8K
     * 相关企业
     * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
     *
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent(int[] nums, int k) {

        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }

        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> {
            return o1[1] - o2[1];
        });

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (queue.size() < k) {
                queue.add(new int[]{entry.getKey(), entry.getValue()});
            } else {
                if (entry.getValue() > queue.peek()[1]) {
                    queue.poll();
                    queue.add(new int[] {entry.getKey(), entry.getValue()});
                }
            }
        }

        //定义数组
        int[] res = new int[k];
        //将优先队列中的值依次弹出
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll()[0];
        }
        return res;
    }



    public static void main(String[] args) {
        Solution so = new Solution();
        so.evalRPN(new String[]{"4", "13", "5", "/", "+"});
    }

}
